package com;

import org.springframework.aop.framework.ProxyFactory;
import org.springframework.context.support.ClassPathXmlApplicationContext;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] nums = {5, 3, 8, 1, 7, 4};
        quickSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }

    public static void bubbleSort3(int[] nums) {
        int flag = nums.length;
        int k = nums.length;
        while (flag > 0) {
            k = flag;
            flag = 0;
            for (int i = 1; i < k; i++) {
                if (nums[i - 1] > nums[i]) {
                    swap(nums, i - 1, i);
                    flag = i;
                }
            }
        }
    }

    public static void bubbleSort2(int[] nums) {
        boolean flag = true;
        int k = nums.length;
        while (flag) {
            flag = false;
            for (int i = 1; i < k; i++) {
                if (nums[i - 1] > nums[i]) {
                    swap(nums, i - 1, i);
                    flag = true;
                }
            }
            k--;
        }
    }

    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length - i; j++) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j - 1, j);
                }
            }
        }
    }

    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    private static void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int partition = partition2(nums, lo, hi);
        quickSort(nums, lo, partition - 1);
        quickSort(nums, partition + 1, hi);
    }

    private static int partition3Ways(int[] nums, int lo, int hi) {
        int temp = nums[lo];
        int lt = lo, gt = hi + 1, i = lo + 1;
        while (i < gt) {
            if (nums[i] < nums[lo]) {
                swap(nums, i, lt + 1);
                i++;
                lt++;
            } else if (nums[i] == nums[lo]) {
                i++;
            } else {
                swap(nums, i, gt - 1);
                gt--;
            }
        }
        swap(nums, lo, lt);
        return lt;
    }

    private static int partition2(int[] nums, int lo, int hi) {
        int temp = nums[lo];
        while (lo < hi) {
            while (lo < hi && nums[hi] >= temp) {
                hi--;
            }
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] <= temp) {
                lo++;
            }
            nums[hi] = nums[lo];
        }
        nums[lo] = temp;
        return lo;
    }

    private static int partition(int[] nums, int lo, int hi) {
        int temp = nums[lo];
        int i = lo + 1, j = hi;
        while (true) {
            while (i <= hi && nums[i] <= temp) {
                i++;
            }
            while (j >= lo + 1 && nums[j] >= temp) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, lo, j);
        return j;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid - 1);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    public static void mergeSort(int[] nums) {
        for (int i = 1; i <= nums.length; i += i) {
            for (int j = 0; j < nums.length; j += i + i) {
                merge(nums, j, j + i - 1, j + i + i - 1);
            }
        }
    }

    private static void merge(int[] nums, int lo, int mid, int hi) {
        int[] temp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= hi) {
            temp[k++] = nums[j++];
        }
        for (int n = lo; n <= hi; n++) {
            nums[n] = temp[n - lo];
        }
    }

}
